package com.lw.leetcode.binary.a;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * binary
 * 1287. 有序数组中出现次数超过25%的元素
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/14 17:48
 */
public class FindSpecialInteger {

    public static void main(String[] args) {
        FindSpecialInteger test = new FindSpecialInteger();
//        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,12,12,12};
        int[] arr = { 1,2,2,6,6,6,6,7,10};
        int specialInteger = test.findSpecialInteger(arr);
        System.out.println(specialInteger);
    }


    public int findSpecialInteger(int[] arr) {
        int len = arr.length;
        int s = len >> 2;
        if (arr[0] == arr[s]) {
            return arr[0];
        }
        for (int i = s; i < len; i += s) {
            int index = find(arr, arr[i], i, Math.min(i + s, len - 1));
            if (arr[index] == arr[i]) {
                return arr[i];
            }
            index--;
            if (arr[index] == arr[index - s]) {
                return arr[index];
            }
        }
        return -1;
    }

    private int find(int[] arr, int target, int st, int end) {
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (arr[m] > target) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }



    public int findSpecialInteger1(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i += len / 4) {
            if (i == 0) {
                if (arr[len / 4] == arr[0]) {
                    return arr[0];
                }
            } else {
                int left = findLeft(arr, arr[i], 0, i);
                if (arr[left + len / 4] == arr[left]) {
                    return arr[left];
                }
            }
        }
        return -1;
    }

    private int findLeft(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1;
        } else if (low == high) {
            if (arr[low] == target) {
                return low;
            } else {
                return -1;
            }
        }
        int mid = (low + high) >> 1;
        if (arr[mid] == target) {
            return findLeft(arr, target, low, mid);
        } else if (arr[mid] > target) {
            return findLeft(arr, target, low, mid - 1);
        } else {
            return findLeft(arr, target, mid + 1, high);
        }
    }
}
